package june7_13;

/*
 * Modify Boolean MATRIX
 * Given a boolean matrix mat[M][N] of size M X N,
 * modify it such that if a matrix cell mat[i][j] is 1 (or true) then
 * make all the cells of ith row and jth column as 1.
 * 
 *  Solve it in a normal Way
 *  1	- Can use another 2d array to copy the matrix, and verify and fill ones here
 *  2	- Have two external 1D array for row and col, fill the ith position of row array, and jth position of col array, if array[i][j] is 1
 *  		then fill the entire row, based on row array values, and entire col based on col array values *   
 *  
 *  Solve it with the use of Space Complexity O(1)
 *  3	- have two flags to find if the first row has 1 and first column has one
 *  	- Use the first row and first column as the external array for solving the matrix[m-1][n-1]
 *  	- Based on the row and col flags stored, fill the first row and first column 
 *  
 *  Solve it without using external space
 *  4. 	For every 1 in the matrix, change the 0 entries of entire row and column with a constant
 *  	On second pass on the matrix, if the entry is constant, change it to 1 
 */
public class BooleanMatrixModification
{

	static int[][] solutionWithExternalArray (int[][] array)
	{
		int rows = array.length;
		int cols = array[1].length;

		int[] rowFlags = new int[rows];
		int[] colFlags = new int[cols];

		for (int i = 0; i<rows; i++)
		{
			for (int j = 0; j<cols; j++)
			{
				if (array[i][j] == 1)
				{
					rowFlags[i] = 1;
					colFlags[j] = 1;
				}
			}
		}

		for (int i = 0; i<rows; i++)
		{
			for (int j = 0; j<cols; j++)
			{
				if (rowFlags[i] == 1 ||
						colFlags[j] == 1)
				{
					array[i][j] = 1;
				}
			}
		}

		return array;
	}

	private static int [][] solutionWithoutExternalArray (int [][] array)
    {
		int rows = array.length;
		int cols = array[0].length;
		
	    int rowFlag = 0, colFlag = 0;
	    
	    // Traverse First Row
	    for (int j = 0; j < cols; j++)
	    {
	    	if (array[0][j] == 1)
	    	{
	    		rowFlag = 1;
	    		break;
	    	}
	    }

	    // Traverse First Column
	    for (int i = 0; i < rows; i++)
	    {
	    	if (array[i][0] == 1)
	    	{
	    		colFlag = 1;
	    		break;
	    	}
	    }
	    
//	    Do the same as solution with external array, whereas use the first row and column as the external array
	    for (int i = 1; i<rows; i++)
		{
			for (int j = 1; j<cols; j++)
			{
				if (array[i][j] == 1)
				{
					array[i][0] = 1;
					array[0][j] = 1;
				}
			}
		}

		for (int i = 1; i<rows; i++)
		{
			for (int j = 1; j<cols; j++)
			{
				if (array[i][0] == 1 ||
						array[0][j] == 1)
				{
					array[i][j] = 1;
				}
			}
		}
		
		// Set the first row ans first column
		if (rowFlag == 1)
		{
			for (int j = 0; j < cols; j++)
            {
				array[0][j] = 1;
            }
		}
		
		if (colFlag == 1)
		{
			for (int i = 0; i < rows; i++)
            {
				array[i][0] = 1;
            }
		}
		
	    return array;
    }
	
	static int[][] solutionWithoutAnyExternalArray (int[][] array)
	{
		int CONST = -1;

		int rows = array.length;
		int cols = array[0].length;

		for (int i = 0; i<rows; i++)
		{
			for (int j = 0; j<cols; j++)
			{
				if (array[i][j] == 1)
				{
					for (int k = 0; k < rows; k++)
					{
						if (array[k][j] == 0)
							array[k][j] = CONST;
					}

					for (int k = 0; k < cols; k++)
					{
						if (array[i][k] == 0)
							array[i][k] = CONST;
					}
				}
			}
		}

		for (int i = 0; i<rows; i++)
		{
			for (int j = 0; j<cols; j++)
			{
				if (array[i][j] == CONST)
				{
					array[i][j] = 1;
				}
			}
		}

		return array;
	}
	
	static void print (int[][] array)
	{
		int rows = array.length;
		int cols = array[0].length;
		
		for (int i = 0; i<rows; i++)
		{
			for (int j = 0; j<cols; j++)
			{
				System.out.print (array[i][j]);
			}
			System.out.println ();
		}
	}

	public static void main (String [] args)
    {
	    int[][] array = new int[][]
	    		{
	    		 { 0, 0, 0, 0 },
	    		 { 0, 1, 0, 0 },
	    		 { 0, 0, 0, 0 },
	    		 { 0, 0, 0, 1 } };
	    
	    print(solutionWithExternalArray (array));
	    // Time Complexity : O (M * N)
	    // Auxillary Space : O (M + N)
	    
	    System.out.println ();
	    
	    array = new int[][]
	    		{
	    		 { 0, 0, 0, 0 },
	    		 { 0, 1, 0, 0 },
	    		 { 0, 0, 0, 0 },
	    		 { 0, 0, 0, 1 } };
	    
	    print(solutionWithoutExternalArray (array));
	    // Time Complexity : O (M * N)
	    // Auxillary Space : O (1)

	    System.out.println ();
	    
	    array = new int[][]
	    		{
	    		 { 0, 0, 0, 0 },
	    		 { 0, 1, 0, 0 },
	    		 { 0, 0, 0, 0 },
	    		 { 0, 0, 0, 1 } };
	    
	    print(solutionWithoutAnyExternalArray (array));
	    // Time Complexity : O (M * N) - this reduces the overhead of 


	    System.out.println ();
	    
    }

	
}
